package sumpayTest7;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;



public class BRtree<Key extends Comparable<Key>,Value> {
private	static final boolean RED =true;
private	static final boolean BLACK =false;
//private  Comparator<? super Integer> comparator;
//public BRtree(Comparator<? super Integer> comparator) {
//    this.comparator = comparator;
//}
//private  class Node{
//	
//	Key key;
//	Value value;
//	Node left,right;
//	boolean color;
//	int n;
//	Node(Key key, Value value, int n, boolean color) {
//		super();
//		this.key = key;
//		this.value = value;
//		this.n=n;
//		this.color = color;
//	}
//}
	private boolean isRed(Node node){
		if(node==null){
			return false;
		}
		return node.color==RED;
		}
	
	Node tleft(Node x){
		Node y=x.right;
		x.right=y.left;
		y.left=x;
		y.color=x.color;
		x.color=RED;
		y.n=x.n;
		x.n=1+size(x.left)+size(x.right);
		return y;
		
	}
	public int size(Node x){
		if(x==null){return 0;}
		else{return x.n;}
	}
	public void flipc(Node node){
		node.color=RED;
		node.left.color=BLACK;
		node.right.color=BLACK;
	}
	Node tright(Node x){
		Node y=x.left;
		x.left=y.right;
		y.right=x;
		y.color=x.color;
		x.color=RED;
		y.n=x.n;
		x.n=1+size(x.left)+size(x.right);
		return y;
	}
	Node root;
	//private class Node;
	public void put(Key key,Value value){
		root=put(root,key,value);
		root.color=BLACK;
			
	}
	public Node put(Node node,Key key,Value value) {
		if(node==null){
			return new Node(key, value, 1, RED);
		}else {
			
			int m= key.compareTo((Key) node.key);
			if(m<0){
				node.left=put(node.left, key, value);
			}else if(m>0){
				node.right=put(node.right, key, value);
			}else {
				node.value=value;
			}
		if(isRed(node.right)&&!isRed(node.left)){
			node=tleft(node);
		}
		if(isRed(node.left)&&isRed(node.left.left)){
			node=tright(node);
		}
		if(isRed(node.left)&&isRed(node.right)){
			flipc(node);
		}
		node.n=size(node.left)+size(node.right)+1;
		return node;
		}
	}
	public void remove() {

	}
//	public void select() {
//
//	}
	public void print(){
		
	}
	public Key select(int k){
		return  (Key) select(root,k).key;
	}
	private Node select(Node node,int k){
		if(node==null){return null;}
		int t=size(node.left);
		if(t>k){ return select(node.left, k);}
		else if(t<k){return select(node.right,k-t-1);}
		else{ return node;}
		
	}
	 List<Key> result = new ArrayList<Key>(); 
	 public List<Key> preorderTraversal(Node root) {    
		 dfs(root);   
		 return result;  
	 } 
	 private void dfs(Node root) {     
		 if (root != null) { 
			 result.add((Key) root.key);  
			 dfs(root.left);  
			 dfs(root.right);
		 }     
	 } 
	 public void delete(Key key){
		 if(!isRed(root.left)&&!isRed(root.right))
			 root.color=RED;
		 	 root=delete(root,key);
		  if(!isEmpty()) root.color=BLACK;
		   
	 }
	 public Node delete(Node h,Key key){
			if(key.compareTo((Key) h.key)<0)
			{
				if(!isRed(h.left)&&!isRed(h.left.left))
						h=moveRedLeft(h);
				h.left=delete(h.left, key);
			}
			else{
				if(isRed(h.left)){
					h=tright(h);
				}
				if(key.compareTo( (Key) h.key)==0&&(h.right==null)){
					return null;
				}
				if(!isRed(h.right)&&!isRed(h.right.left)){
					h=moveRedLeft(h);
				}
				if(key.compareTo( (Key) h.key)==0){
					h.value=get(h.right,(Key) min(h.right).key );
					h.key=min(h.right).key;
					h.right=deleteMin(h.right);
				}
				else h.right=delete(h.right, key);
			}
			return balance(h);  
		 }
	 public Key min(){
		 return (Key) min(root).key;
	 }
	 public Node min(Node x){
		 if(x.left==null) return x;
		 return min(x.left);
	 }
	 public Value get(Key key){
		 return get(root,key);
	 }
	 public Value get(Node node,Key key){
		 if(node==null) return null;
		 int c=key.compareTo((Key) node.key);
		 if(c<0) return get(node.left,key);
		 else if(c>0) return get(node.right,key);
		 else return (Value) node.value;
	 }
	
	 public void deleteMin() {
		 if(!isRed(root.left)&&!isRed(root.right))
			 root.color=RED;
		 root=deleteMin(root);
		 if(!isEmpty()) root.color=BLACK;
	 }
	 private boolean isEmpty() {
		return root==null;
	}
	private Node deleteMin(Node h) {
		if(h.left==null)
		return null;
		if(!isRed(h.left)&&!isRed(h.left.left))
			h=moveRedLeft(h);
		h.left=deleteMin(h.left);
		return balance(h);
	}
	private Node moveRedLeft(Node h){
		 flipcolor1(h);
		 if(isRed(h.right.left)){
			 h.right=tright(h.right);
			 h=tleft(h);
		 }
		return h;
	 }
	 private void flipcolor1(Node h) {
		  if(h.left != null)
	            h.left.color = flip(h.left) ;
	        if(h.right != null)
	            h.right.color = flip(h.right) ;
	        h.color = flip(h) ;
		
	}
	private boolean flip(Node h) {
		return !h.color;
	}
	public Node balance(Node node){
			if(isRed(node.right)&&!isRed(node.left)){
				node=tleft(node);
			}
			if(isRed(node.left)&&isRed(node.left.left)){
				node=tright(node);
			}
			if(isRed(node.left)&&isRed(node.right)){
				flipc(node);
			}
			node.n=size(node.left)+size(node.right)+1;
			return node;
	 }
	 public static void main(String[] args) {
			BRtree<String, String> b=new BRtree<String, String>();
//			b.put("r", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("e", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("a", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//		
//			b.put("s", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//		
//			b.put("C", "dsdsa");
//			b.put("13", "dsdsa");
//			b.put("12", "dsdsa");
//			Node node=b.root;
//			List<String> list=b.preorderTraversal(node);
//			for (String string : list) {
//				System.out.print(string+" ");
//			}
//			System.out.println(b.root.key);
//			b.root.PreOrderPrint();
			//b.root.LevelOrderPrint();
			
			
			
//			b.put("A", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("B", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("C", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("D", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
			
			Random random= new Random();
			HashSet<Integer> hash=new HashSet<Integer>();
			for (int i = 1; i < 60; i++) {
				hash.add(random.nextInt(10));
//			hash.add(i);
			}
			for (Integer integer : hash) {
				String s="";
				s=s+integer;
				b.put(s, "dsdsa");
				System.out.println("-----------------------------");
				b.root.LevelOrderPrint();
			}
//			b.put("s", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("e", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("a", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("r", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("c", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("h", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("x", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("m", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("p", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			b.put("l", "dsdsa");
//			System.out.println("-----------------------------");
//			b.root.LevelOrderPrint();
//			for (int i = 0; i < 10; i++) {
//				System.out.print(b.select(i));
//			}
			b.delete("2");
			System.out.println("-----------------------------");
			b.root.LevelOrderPrint();
		} 
}
